package com.xzz.backtrack;



/**
 * @author: hhz
 * @create: 2022-02-28 14:27
 * 1601. 最多可达成的换楼请求数目
 **/
public class MaximumRequests {

    public static void main(String[] args) {
        System.out.println(maximumRequests(5, new int[][]{{0, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 0}, {3, 4}}));
        System.out.println(maximumRequests(5, new int[][]{{0, 0}, {1, 2}, {2, 1}}));
    }
    static int[] ans ;
    static int max = 0;
    public static int maximumRequests(int n, int[][] requests) {
        ans = new int[n];
        max = 0;
        backtrack(0,0,requests);
        return max;
    }

    public static void backtrack(int i, int res,int[][] requests) {
        if(i>=requests.length){
            if(check()){
                max = Math.max(res,max);
            }
            return;
        }
        int x = requests[i][0];
        int y = requests[i][1];
        ans[x]--;
        ans[y]++;
        backtrack(i+1,res+1,requests);
        ans[x]++;
        ans[y]--;
        backtrack(i+1,res,requests);
    }
    public static boolean check(){
        for(int i = 0;i<ans.length;i++){
            if(ans[i]!=0) return false;
        }
        return true;
    }
}
